1. Field of the Invention
The invention relates to computer vision techniques and, more particularly, to apparatus and methods for automatically tracking objects contained in image sequences.
2. Description of the Prior Art
In the field of computer vision, active contours have been used to detect and track objects of interest in a sequence of digital images. Computer systems capable of tracking active contours have been successfully used to perform a variety of image processing tasks, such as deleting, enhancing, coloring, reshaping or otherwise modifying selected objects in digital images according to some predetermined criteria. Although contour tracking systems have served the purpose, they have not proved entirely reliable in many image processing applications where it is necessary to track complex, deformable and/or articulated objects.
Active contour tracking essentially involves the process of segmenting a first image into separate regions and then tracking these regions through time from a sequence of similar images. Segmenting a digital image, which typically comprises an array of pixels, involves the process of identifying which pixel belongs to which region. Data is then generated which identifies sets of pixels that represent a contour that approximately outlines a distinct feature, such as an edge or a ridge, that defines the regions of interest. In many applications, the regions may be relatively uncomplicated and can be approximated with simple geometric shapes, such as circles, rectangles, ellipses, or others. However, since many natural objects cannot be described by simple geometric shapes, techniques have been developed to represent an edge or a ridge on these objects with more complex contours than those simple shapes. One important prior art technique for modeling complex shapes with active contours involves the use of "snakes." The following article describes a snake technique in detail: Kass et al, "Snakes: Active Contour Models," International Journal of Computer Vision, Vol. 2, pp 321-331, 1988.
In general, a snake is an energy-minimizing active contour that is guided by external constraint forces and influenced by image forces that pull it toward features of interest such as lines, ridges and edges of an object. A typical energy or cost function for a snake may contain terms that measure the smoothness of the contour and the amount of edge strength along the contour. The goal is to minimize this function to find an optimal contour which is smooth and coincides with high-gradient magnitude points in the image. The Kass et al article proposes to minimize an energy or cost function using Euler equations and gradient descent.
A disadvantage of most snake techniques is that they can be very dependent on the starting points of the contour. The energy or cost minimization processes in snake techniques are usually based solely on gradient descent and are not guaranteed to locate a global minimum of the corresponding function. As a result, neighboring edges can be very distracting to such a process. Hence, depending on the initial contour configuration, different local minima of the corresponding function may be reached, thereby failing to find the optimal contour.
Another image tracking technique involves the use of "level sets", which have been used to model moving boundaries between two regions in physical phenomenon, such as an interface between ice and water at the polar regions, or an interface between fire and grass in a brush fire. In such situations, it is difficult to model the evolution of the contour and prevent the contour from crossing over itself. The level set approach builds an original curve into a surface called a "level set function". Then, instead of moving the curve, the level set function expands, rises and falls. The advantage of this technique is that the level set function is very well behaved; thus, topological changes which break the curve or merge two different curves are handled naturally. Also, this method extends very easily in three dimensions to model moving surface interfaces.
Unfortunately, the level set technique is primarily designed for tracking homogeneous objects. Also, it has been recognized that this technique requires symmetric initialization in the sense that if the initial contour is placed close to part of an object boundary, the contour can cross over that portion before reaching the other portions of the object boundary. In addition, if there are gaps in the object boundary, the level set will pass through the gaps without capturing the object of interest. In level set models, the contour usually slows down around image edges, but it does not come to a complete stop unless the edge is an ideal edge. For real edges, therefore, the contour has to be stopped in an ad-hoc manner.
A popular solution for locating the global optimum of a cost function involves a searching procedure that uses a graph exploration technique. Prior art graph exploration techniques have been primarily applied to extracting objects in a single image. Since it is difficult to model the shape of an object for tracking purposes, graph exploration techniques for contour extraction have had very limited success in tracking applications. Consequently, a need exists for image tracking systems capable of locating the global optimum of a cost function that combines shape and image information for a well defined active contour in an image sequence.